package com.github.MaxPQ;

public class MaxPQ{
        private Comparable[] pq;
        private int N=0;
        public MaxPQ(int maxN){
            pq=new Comparable[maxN+1];
        }
        public boolean isEmpty(){
            return N==0;
        }
        public int size(){
            return N;
        }
        public void insert(Comparable v){
            pq[++N]=v;
        }
        public Comparable delMax(){
            Comparable max=pq[1];
            exch(1,N--);
            pq[N+1]=null;
            sink(1);
            return max;
        }
        private boolean less(int i,int j){
            return pq[i].compareTo(pq[j])<0;
        }
        private void exch(int i,int j) {
            Comparable temp=pq[i];
            pq[i]=pq[j];
            pq[j]=temp;
        }
        private void swim(int k){
            while (k>1&&less(k/2,k)){
                exch(k/2,k);
                k=k/2;
            }
        }
        private void sink(int k){
            while (2*k<=N){
                int j=2*k;
                if (j<N&&less(j,j+1))j++;
                if (!less(k,j))break;
                exch(k,j);
                k=j;
            }
        }
}
